lib/Mi manual de algoritmos/version_actual/src/java/io_estandar.java

   1 import java.util.*;
   2 import java.io.*;
   3 import java.math.*;
   4
   5 class Main {
   6     public static void main(String[] args) throws IOException {
   7       BufferedReader reader =
   8         new BufferedReader(new InputStreamReader(System.in));
   9       String line = reader.readLine();
  10       StringTokenizer tokenizer = new StringTokenizer(line);
  11       int N = Integer.valueOf(tokenizer.nextToken());
  12       while (N-- > 0){
  13         String a, b;
  14         a = reader.readLine();
  15         b = reader.readLine();
  16
  17         int A = a.length(), B = b.length();
  18         if (B > A){
  19           System.out.println("0");
  20         }else{
  21           BigInteger dp[][] = new BigInteger[2][A];
  22           /*
  23             dp[i][j] = cantidad de maneras diferentes
  24             en que puedo distribuir las primeras i
  25             letras de la subsecuencia (b) terminando
  26             en la letra j de la secuencia original (a)
  27           */
  28
  29           if (a.charAt(0) == b.charAt(0)){
  30             dp[0][0] = BigInteger.ONE;
  31           }else{
  32             dp[0][0] = BigInteger.ZERO;
  33           }
  34           for (int j=1; j<A; ++j){
  35             dp[0][j] = dp[0][j-1];
  36             if (a.charAt(j) == b.charAt(0)){
  37               dp[0][j] = dp[0][j].add(BigInteger.ONE);
  38             }
  39           }
  40
  41           for (int i=1; i<B; ++i){
  42             dp[i%2][0] = BigInteger.ZERO;
  43             for (int j=1; j<A; ++j){
  44               dp[i%2][j] = dp[i%2][j-1];
  45               if (a.charAt(j) == b.charAt(i)){
  46                 dp[i%2][j] = dp[i%2][j].add(dp[(i+1)%2][j-1]);
  47               }
  48             }
  49           }
  50           System.out.println(dp[(B-1)%2][A-1].toString());
  51         }
  52       }
  53     }
  54 }